1. Field of the Invention
The present invention relates to a decoding unit for decoding input codes as well as circuitry for performing preprocessing for a predetermined processing in the decoding processing. More particularly, the invention relates to a construction of a circuit unit for decoding Low Density Parity Check (LDPC) codes.
2. Description of the Background Art
For constructing a data communication system, such performances are required as fast communication, low power consumption, and high communication quality (low bit error rate). An error correction technique for detecting and correcting errors in received codes has been widely utilized, as one of techniques satisfying the above requirements, in wireless, cable and record systems and others.
In recent years, attention has been given to LDPC (Low Density Parity Check) codes and sum-product algorithm as such error correction technique. The decoding operation utilizing the LPDC codes is discussed the article by S. Y. Chung et al., “On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit,” IEEE COMMUNICATIONS LETTERS, Vol. 5, No. 2, February 2001, pp. 58-60. The Chung reference discloses that decoding characteristics of 0.04 dB to the Shannon limit of the white Gaussian communication channel can be achieved by utilizing a rate—½ irregular LDPC codes. The irregular LDPC codes are such codes that a row weight (number of “1” set in a row) and a column weight (number of “1” set in a column) in a parity check matrix are not constant. The LDPC codes, for which the row weight and the column weight are constant in each row and each column, are referred to as regular LDPC codes.
Chun discloses a mathematical algorithm for decoding the LDPC codes according to the sum-product algorithm, but fails to show a hardware implementation for specifically performing a huge amounts of calculations involved.
An article by Yeo et al., “VLSI Architectures for Iterative Decoders in Magnetic Recording Channels,” IEEE Trans. Magnetics, Vol. 37, No. 2, March 2001, pp. 748-755 discusses a circuit construction of a decoding unit of LDPC codes. According to the Yeo reference, a posteriori probability of information symbol based on reception series is calculated according to MAP (maximum a posteriori probability) algorithm based on trellis, i.e., BCJR algorithm. In the trellis, forward iteration and backward iteration are calculated for each state, and the a posteriori probability is obtained based on the forward and backward iteration values. In this calculation equations, Add-Compare-Select-Add units are used for the calculations. In calculation of LDPC codes, the units are configured such that a parity check matrix is generated according to the sum-product algorithm, and an estimated value is calculated by utilizing values received from different check nodes.
Wadayama discusses in the article, “Low Density Parity Check Codes and the Sum-Product Algorithm,” Technical Report of IEICE, MR 2001-83, December 2001, the LDPC codes and the sum-product algorithm as well as min-sum algorithm in a log-domain. In Wadayama, it is disclosed that processing according to an f-function of Gallager can be implemented only with four kinds of fundamental operations, or addition, minimization, positive/negative determination, and multiplication of positive and negative signs.
According to Yeo and Wadayama, for generating a parity check matrix to calculate a first order estimated word, an outer value log-ratio α (log-ratio of outer information) is updated with the f-function of Gallager according to sum-product algorithm, and then a priori value log-ratio β (log-ratio of a priori information) of symbol is calculated based on the outer value log-ratio. Therefore, the operation of the Gallager function requires a long time and an increased unit scale.
Wadayama suggests that the sum-product decoding algorithm is equivalent to the min-sum decoding algorithm, and use of the min-sum decoding algorithm can simplify practical circuit construction. Even with the min-sum decoding algorithm, however, in the Min operation of calculating a minimum value by using a parity check matrix, the minimum value is obtained by performing the Min operation for each element. Therefore, elements of arithmetic operation targets increase in number with increase in code length, so that a processing time is likewise increased and the scale and complexity of the decoding unit are increased.